1. Field of the Invention
This invention relates to the transmission of images, and in particular to an efficient method for coding images, transmitting signals representative of the codes representing the images to a receiver and to the set of characters making up a font used to replicate an image, and to the efficient selection of an optimum font for this purpose.
2. Prior Art
An important way of communicating information of a business or technical nature is by use of line art such as drawings, schematics, diagrams, signatures, logos and various conventional symbols such as the letters, numerals and punctuation marks of ordinary written or printed communications or such special symbols as are employed in a particular trade or profession. Line art is generally produced by the drawing of a pen, pencil, or brush on paper. The consequence of this is twofold. In the first place, line drawings consist of marks in one color on background in another color; for example, black on white. Secondly, the marks produced in line art are generally narrow and long. That means that each component of a line drawing, considered as a region in a two-dimensional space, has generally two distinct measurements in perpendicular directions which can be denoted as the lengths and the widths of a stroke, with width being much smaller than length.
The development of technology for transforming optical signals representing images into electronic form, processing these electronic signals by means of highly efficient digital logic methods, and reproducing or displaying the images in human accessible form, has made feasible the cost-effective storage, transmission, and subsequent reproduction or display of images, including in particular, line art as discussed above. This technology promises the automatic storage and retrieval of letters, and other documents considered as line art (such as checks, bills of lading, credit cards, slips, etc.), the transmitting of such letters and other information in the form of electronic signals, and the bypassing of slower and possibly more expensive mail. The subsequent presentation of the information to the human addressee can be transitory using, for example, a cathode ray tube display, or permanent, by forming a replica on paper.
One factor that inhibits the rapid evolution and acceptance of electronic image processing is the large quantity of information that is contained in a digitized image and the resulting high cost of storage and transmission and slowness of printing. The following numbers will clarify this remark. In order to achieve printing of acceptable office quality, a density of about 300 dots per inch is necessary. For high quality printing perhaps twice this density is required. Therefore, to represent with adequate quality the image content of an 8.5" by 11" page by means of black and white dots, a total of about 8.5 million black and white dots must be stored. This is such a large number that even in the memory of large computers at most a few pages can be stored. Small computers, whose selection is dictated by cost considerations, can hold only a fraction of a page. In transmission and reproduction of images, the large number of dots required to represent an image results either in the use of extremely expensive but fast apparatus, or else in correspondingly slow transmission and reproduction rates. The result in either case is that the production cost per unit of time is high.
The method of overcoming this high cost of production per unit time is to transform the image into a smaller number of black and white dots, or more generally, units of information termed "bits" in the literature. For one-dimensional signals there is a rich literature beginning with the work of Claude Shannon on effective methods of transforming signals for efficient transmission. Transformations of this nature which are reversible (i.e., capable of perfectly reproducing the original image from the code), are called codes or coding schemes. A good summary of this work is found in Robert J. McEliece's book The Theory of Information and Coding: A Mathematical Framework for Communication, Redding, Mass. Addison-Wesley 1977. Much less work has been done in the area of two-dimensional encoding (See the article by Frank entitled "High Fidelity Encoding of Two-Level, High Resolution Images," Proceedings 1973 International Conference on Communications, 1EEE, June 1973). Past work on encoding has emphasized as essential the faithful reproduction of the original information. The problems of efficient image encoding, however, underscore the essential subjective nature of reproduction of images.
The number of bits required to represent a given area of an image has been defined as N.sup.2 bits per square inch (where N represents the number of bits per linear inch) by Knudson in a paper entitled "Digital Encoding of Newspaper Graphics" dated August 1975, and issued by the Massachusetts Institute of Technology Electronic Systems Laboratory, Cambridge, Mass., Report No. ESL-R-616. Knudson, in this paper, describes work toward reducing or minimizing the number of information bits required to represent the image, and at the same time yield printed copy that closely approximates the high quality of the original. To do this, Knudson recognizes that meaningful images are not completely random collections of elements, but that the inherent structure of images can often be utilized to define a set of characters for use in reproducing the image which reduces storage requirements.
As explained by Knudson, a common data compression technique is called "run-length coding." This technique comprises the compression of image data by applying codes to the run-lengths of identical elements of the image rather than to each individual element itself. The data compression achieved depends upon pictorial content, but compression ratios for one-dimensional run-length codes commonly range from two to four for typical images.
Kundson discloses a second technique for reducing the amount of data to be transmitted during image transfer called "two-dimensional run-length codes". This technique codes only the differences between run-lengths from one line to the next, rather than the run-lengths themselves. Since adjacent scan lines tend to contain similar bit patterns, the differences between run-lengths tend to be smaller numbers than the actual run-lengths, and fewer bits are needed to code them. An average data compression ratio of approximately fourteen to one has allegedly been obtained for the transmission of complete newspaper pages, including text and advertising artwork.
Knudson discloses another technique for reducing the data transmission rate required to transmit a given image. Knudson discloses the individual encoding of small square segments of the image by partitioning the image into small blocks or "subpictures.38 A block pattern is then selected from a predetermined set of patterns for each subpicture of the image so as to approximate closely the image within that block. According to Knudson, his technique permits finer image detail than the prior art techniques (which included a half-tone technique using dots of different diameters to represent the average gray level over a subpicture area) because the patterns used to represent the various blocks have a greater variety of shapes compared to the prior art uniformly shaped half-tone dots. Knudson discloses the use of 62 patterns (see FIG. 2 of Knudson U.S. Pat. No. 4,281,312) excluding the all white pattern which is never printed. Each pattern is typically produced by an array of appropriately colored dots. Unfortunately, the system of Knudson yielded results of insufficient quality. Data compression was relatively inefficient.
The printing or displaying of images by means of minute elements such as circular (or square) marks or "dots" of one color on a background of another color (as done by Knudson) is well known in the art. The quality of the reproduction depends on the number of dots per unit area. For superior quality, the number of dots per square inch must exceed one million. Excellent quality can be achieved with a density of two hundred fifty thousand (250,000) dots per square inch. Good commercial and office quality is produced at densities between sixty thousand (60,000) and one hundred thousand (100,000) dots per square inch. Computer output printers and displays produce alphanumeric characters and images at densities between about four thousand (4,000) and forty thousand (40,000) dots per square inch. Table 1 below summarizes this information by correlating density of print elements with print quality. The density is expressed in linear dimensions as number of dots per inch. The corresponding two-dimensional density is merely the square of this quantity.
TABLE 1 ______________________________________ Density (dots/inch) Print Quality ______________________________________ Greater than 1,000 Superior (graphic arts, fine arts) 500 to 1,000 Excellent (quality magazines) 250 to 500 Good Commercial and office (Executive correspondence) 60 to 250 Computer output quality ______________________________________
A known method of rendering photographs for reproduction in print is known as half-tone screening. In this method, the photograph is divided into a grid of squares and for printing, each square is replaced by one occupied by a "dot" whose size is proportional to the area density. That is, the ratio of the dot area to the area of the square closely approximates the density in the square. In this method of reproduction, the resolution, that is, the number of squares per inch (also called the mesh), is also closely correlated with the quality. Table 2 below shows the correlation between quality of reproduction and mesh. An additional parameter is also introduced. This is the number of distinct gray levels and equals the number of distinct "dot" sizes and shapes.
TABLE 2 ______________________________________ Mesh (No. of No. of squares/inch) Gray Levels Quality ______________________________________ Greater than Greater than or Superior (fine arts, or equal to 150 equal to 64 graphic arts) 120-150 32 Excellent (quality magazines) 65-120 16 Good commercial (inplant printing, newspapers) less than 65 16 or less Utility ______________________________________
The known art of half-tone reproduction has an important feature in common with Knudson's disclosure. In all the instances mentioned, an image is analyzed in elementary parts, squares in the case of half-tone reproduction and in Knudson's teaching, and the actual image in each elementary part is replaced by one or another of a set of predetermined patterns. The important criteria for comparing and judging the quality of image reproduction are the design of the set of patterns, the methods for assigning a specific pattern to a given image element, and the degree of compression achieved in relation to the quality. Knudson states that "62 patterns and approximately 125 subpictures per inch represent a reasonable compromise between image quality and storage requirements. Under these conditions, slightly less than 10.sup.5 bits are needed to store each square inch of picture, yielding a compression ratio of 10:1 over point-by-point coding at 1,000 elements per inch resolution."